//寻找旋转排序数组中的最小值
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums.back()) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[right];
    }
};

//在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (!nums.size())
            return {-1, -1};
        vector<int> ret(2);
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target)
                r = mid;
            else
                l = mid + 1;
        }
        if (nums[r] != target)
            return {-1, -1};
        ret[0] = r;
        l = 0;
        r = nums.size() - 1;
          while (l < r) {
              int mid = l + (r - l + 1) / 2;
              if (nums[mid] > target)
                  r = mid - 1;
              else
                  l = mid;
          }
        ret[1] = l;
        return ret;
    }
};